package problems

import (
	"container/list"
	"fmt"
	"math"
	"sort"
	"strconv"
	"strings"
)

// 101
// https://leetcode-cn.com/problems/symmetric-tree/
func IsSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	var isMirror func(left *TreeNode, right *TreeNode) bool
	isMirror = func(left *TreeNode, right *TreeNode) bool {
		if left == nil && right == nil {
			return true
		}
		if left == nil || right == nil {
			return false
		}

		return left.Val == right.Val && isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
	}
	return isMirror(root.Left, root.Right)
}

func IsSymmetric2(root *TreeNode) bool {
	if root == nil {
		return true
	}
	var queue []*TreeNode
	var left, right *TreeNode
	queue = append(queue, root.Left)
	queue = append(queue, root.Right)
	for len(queue) > 0 {
		left, right, queue = queue[0], queue[1], queue[2:]
		if left == nil && right == nil {
			continue
		}
		if left == nil || right == nil {
			return false
		}
		if left.Val != right.Val {
			return false
		}
		queue = append(queue, left.Left)
		queue = append(queue, right.Right)
		queue = append(queue, left.Right)
		queue = append(queue, right.Left)
	}
	return true
}

// 102
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
func LevelOrder(root *TreeNode) [][]int {
	var result [][]int
	var level, num = 0, 0
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		num = len(stack)
		result = append(result, []int{})
		for i := 0; i < num; i++ {
			result[level] = append(result[level], stack[i].Val)
			if stack[i].Left != nil {
				stack = append(stack, stack[i].Left)
			}
			if stack[i].Right != nil {
				stack = append(stack, stack[i].Right)
			}
		}
		level++
		stack = stack[num:]
	}
	return result
}

// 103
// https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
func ZigzagLevelOrder(root *TreeNode) [][]int {
	var result [][]int
	var level, num = 0, 0
	var stack []*TreeNode
	var isLeft = true
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		num = len(stack)
		result = append(result, []int{})
		for i := 0; i < num; i++ {
			result[level] = append(result[level], stack[i].Val)
			if stack[i].Left != nil {
				stack = append(stack, stack[i].Left)
			}
			if stack[i].Right != nil {
				stack = append(stack, stack[i].Right)
			}
		}
		if !isLeft {
			for i := 0; i < num/2; i++ {
				result[level][i], result[level][num-i-1] = result[level][num-i-1], result[level][i]
			}
		}
		isLeft = !isLeft
		level++
		stack = stack[num:]
	}
	return result
}

// 104
// https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var left, right = MaxDepth(root.Left) + 1, MaxDepth(root.Right) + 1
	if left < right {
		left = right
	}
	return left
}

// 105
// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
func BuildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 || len(preorder) != len(inorder) {
		return nil
	}
	var index = 0
	for k, v := range inorder {
		if v == preorder[0] {
			index = k
			break
		}
	}
	var node = &TreeNode{Val: preorder[0]}
	node.Left = BuildTree(preorder[1:index+1], inorder[:index])
	node.Right = BuildTree(preorder[index+1:], inorder[index+1:])
	return node
}

// 106
// https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
func BuildTree2(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 || len(postorder) == 0 || len(inorder) != len(postorder) {
		return nil
	}
	var index = 0
	for k, v := range inorder {
		if v == postorder[len(postorder)-1] {
			index = k
			break
		}
	}
	var node = &TreeNode{Val: inorder[index]}
	node.Left = BuildTree2(inorder[:index], postorder[:index])
	node.Right = BuildTree2(inorder[index+1:], postorder[index:len(postorder)-1])
	return node
}

// 107
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
func LevelOrderBottom(root *TreeNode) [][]int {
	var result [][]int
	var index int
	var add func(root *TreeNode, level int)
	add = func(root *TreeNode, level int) {
		if root != nil {
			for len(result) <= level {
				result = append([][]int{{}}, result...)
			}
			index = len(result) - level - 1
			result[index] = append(result[index], root.Val)
			add(root.Left, level+1)
			add(root.Right, level+1)
		}
	}
	add(root, 0)
	return result
}

// 108
// https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
func SortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	var mid = len(nums) / 2
	return &TreeNode{nums[mid], SortedArrayToBST(nums[:mid]), SortedArrayToBST(nums[mid+1:])}
}

// 110
// https://leetcode-cn.com/problems/balanced-binary-tree/
func IsBalanced(root *TreeNode) bool {
	var equal = true
	var nodeDepth func(root *TreeNode) int
	var compareDepth func(root *TreeNode)
	nodeDepth = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		var left, right = nodeDepth(root.Left), nodeDepth(root.Right)
		if left > right {
			return left + 1
		}
		return right + 1
	}
	compareDepth = func(root *TreeNode) {
		if equal && root != nil {
			if math.Abs(float64(nodeDepth(root.Left)-nodeDepth(root.Right))) > 1 {
				equal = false
			} else {
				compareDepth(root.Left)
				compareDepth(root.Right)
			}
		}
	}
	compareDepth(root)
	return equal
}

// 111
// https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
func MinDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var min = 0
	var findLevel func(root *TreeNode, level int)
	findLevel = func(root *TreeNode, level int) {
		if root != nil {
			if root.Left == nil && root.Right == nil {
				if min == 0 {
					min = level
				}
				if min > level {
					min = level
				}
			} else {
				if root.Left != nil {
					findLevel(root.Left, level+1)
				}
				if root.Right != nil {
					findLevel(root.Right, level+1)
				}
			}
		}
	}
	findLevel(root, 1)
	return min
}

// 112
// https://leetcode-cn.com/problems/path-sum/
func HasPathSum(root *TreeNode, sum int) bool {
	if root == nil {
		return false
	}
	if root.Left == nil && root.Right == nil {
		return root.Val == sum
	}

	return HasPathSum(root.Left, sum-root.Val) || HasPathSum(root.Right, sum-root.Val)
}

// 113
// https://leetcode-cn.com/problems/path-sum-ii/
func PathSum2(root *TreeNode, sum int) [][]int {
	var result [][]int
	var order func(root *TreeNode, sum int, path []int)
	order = func(root *TreeNode, sum int, path []int) {
		if root != nil {
			path = append(path, root.Val)
			if root.Left != nil || root.Right != nil {
				order(root.Left, sum-root.Val, path)
				order(root.Right, sum-root.Val, path)
			} else if root.Val == sum {
				var subPath = make([]int, len(path))
				copy(subPath, path)
				result = append(result, subPath)
			}
		}
	}
	order(root, sum, nil)
	return result
}

// 114
// https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
func Flatten(root *TreeNode) {
	var findRightLeaf func(root *TreeNode) *TreeNode
	findRightLeaf = func(root *TreeNode) *TreeNode {
		if root == nil {
			return nil
		}
		if root.Right == nil {
			return root
		}
		return findRightLeaf(root.Right)
	}
	if root != nil {
		root.Left, root.Right = root.Right, root.Left
		Flatten(root.Left)
		Flatten(root.Right)
		findRightLeaf(root).Right = root.Left
		root.Left = nil
	}
}

// 115
// https://leetcode-cn.com/problems/distinct-subsequences/
func NumDistinct(s string, t string) int {
	m, n := len(s), len(t)
	if n > m {
		return 0
	}
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][n] = 1
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			dp[i][j] = dp[i+1][j]
			if s[i] == t[j] {
				dp[i][j] += dp[i+1][j+1]
			}
		}
	}

	return dp[0][0]
}

// Connect
// 116
// https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
func Connect(root *PerfectTreeNode) *PerfectTreeNode {
	var p1, p2, p3 *PerfectTreeNode = root, nil, root                                      // p1本层最左侧，p2上次父级，p3移动指针
	var findNext func(child, parent *PerfectTreeNode) (*PerfectTreeNode, *PerfectTreeNode) // 返回下一个节点和父节点
	findNext = func(child, parent *PerfectTreeNode) (*PerfectTreeNode, *PerfectTreeNode) {
		if parent == nil {
			return nil, nil
		}
		if child == parent.Left {
			return parent.Right, parent
		}
		if parent.Next == nil {
			return nil, nil
		}
		if parent.Next.Left != nil {
			return parent.Next.Left, parent.Next
		}
		return parent.Next.Right, parent.Next
	}

	for p1 != nil {
		for p3 != nil {
			p3.Next, p2 = findNext(p3, p2)
			p3 = p3.Next
		}
		p2 = p1
		if p1.Left != nil {
			p1 = p1.Left
		} else {
			p1 = p1.Right
		}
	}
	return root
}

// 117
// https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
func Connect2(root *PerfectTreeNode) *PerfectTreeNode {
	if root != nil {
		var stack = []*PerfectTreeNode{root}
		for len(stack) > 0 {
			var num = len(stack)
			var last *PerfectTreeNode
			for _, v := range stack[:num] {
				if last != nil {
					last.Next = v
				}
				if v.Left != nil {
					stack = append(stack, v.Left)
				}
				if v.Right != nil {
					stack = append(stack, v.Right)
				}
				last = v
			}
			stack = stack[num:]
		}
	}
	return root
}

// 118
// https://leetcode-cn.com/problems/pascals-triangle/
func Generate(numRows int) [][]int {
	var res = make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		var subRes = make([]int, i+1)
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				subRes[j] = 1
			} else {
				subRes[j] = res[i-1][j-1] + res[i-1][j]
			}
		}
		res[i] = subRes
	}
	return res
}

// 119
// https://leetcode-cn.com/problems/pascals-triangle-ii/
func GetRow(rowIndex int) []int {
	var res = make([][]int, rowIndex+1)
	for i := 0; i <= rowIndex; i++ {
		var subRes = make([]int, i+1)
		for j := 0; j <= i; j++ {
			if j == 0 || j == i {
				subRes[j] = 1
			} else {
				subRes[j] = res[i-1][j-1] + res[i-1][j]
			}
		}
		res[i] = subRes
	}
	return res[rowIndex]
}

// 120
// https://leetcode-cn.com/problems/triangle/
func MinimumTotal(triangle [][]int) int {
	height := len(triangle)
	if height == 0 {
		return 0
	}
	min, last := math.MaxInt64, math.MaxInt64
	for ik, iv := range triangle {
		for jk := range iv {
			if ik > 0 {
				last = math.MaxInt64
				if jk < ik {
					last = triangle[ik-1][jk]
				}
				if jk > 0 && triangle[ik-1][jk-1] < last {
					last = triangle[ik-1][jk-1]
				}
				triangle[ik][jk] += last
			}
			if ik == height-1 && triangle[ik][jk] < min {
				min = triangle[ik][jk]
			}
		}
	}
	return min
}

// 自底向上
func MinimumTotal2(triangle [][]int) int {
	for i := len(triangle) - 2; i >= 0; i-- {
		for j := 0; j < len(triangle[i]); j++ {
			if triangle[i+1][j] < triangle[i+1][j+1] {
				triangle[i][j] += triangle[i+1][j]
			} else {
				triangle[i][j] += triangle[i+1][j+1]
			}
		}
	}
	return triangle[0][0]
}

// 121
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
func MaxProfit(prices []int) int {
	var min, max = -1, 0
	for _, v := range prices {
		if min == -1 {
			min = v
		} else {
			if max < v-min {
				max = v - min
			}
			if min > v {
				min = v
			}
		}
	}
	return max
}

// 122
// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
func MaxProfit2(prices []int) int {
	var in, out, sum = 0, 0, 0
	for k, v := range prices {
		if v < prices[out] {
			sum += prices[out] - prices[in]
			in = k
		}
		out = k
	}
	if out > in {
		sum += prices[out] - prices[in]
	}
	return sum
}

// 125
// https://leetcode-cn.com/problems/valid-palindrome/
func IsPalindrome(s string) bool {
	var left, right = 0, len(s) - 1
	for left < right {
		var leftS, rightS = s[left], s[right]
		if leftS >= 97 && leftS <= 122 {
			leftS -= 32
		}
		if rightS >= 97 && rightS <= 122 {
			rightS -= 32
		}
		if leftS < 48 || leftS > 90 || (leftS > 57 && leftS < 65) {
			left++
			continue
		}
		if rightS < 48 || rightS > 90 || (rightS > 57 && rightS < 65) {
			right--
			continue
		}
		if leftS != rightS {
			return false
		}
		left++
		right--
	}
	return true
}

// 129
// https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
func SumNumbers(root *TreeNode) int {
	var sum = 0
	var order func(root *TreeNode, subSum int)
	order = func(root *TreeNode, subSum int) {
		if root != nil {
			subSum = subSum*10 + root.Val
			if root.Left == nil && root.Right == nil {
				sum += subSum
			} else {
				order(root.Left, subSum)
				order(root.Right, subSum)
			}
		}
	}
	order(root, sum)
	return sum
}

// 134
// https://leetcode-cn.com/problems/gas-station/
func canCompleteCircuit(gas []int, cost []int) int {
	// 只要供给大于消耗，那么沿途缺油最多的下一站开始
	remain, needed, index := 0, 0, -1 // 油箱还有多少油、缺油最多数量、缺油最多的索引

	for i := 0; i < len(gas); i++ {
		remain += gas[i] - cost[i]

		fmt.Println(i, gas[i], cost[i], remain)
		if remain < needed {
			needed, index = remain, i
		}
	}

	if remain < 0 {
		return -1
	}

	return (index + 1) % len(gas)
}

// 136
// https://leetcode-cn.com/problems/single-number/
func SingleNumber(nums []int) int {
	var res = 0
	for _, v := range nums {
		res = res ^ v
	}
	return res
}

// 138
// https://leetcode-cn.com/problems/copy-list-with-random-pointer/
func CopyRandomList(head *Node) *Node {
	var stackOld, stackNew []*Node
	m, index := make(map[*Node]int), 0
	for head != nil {
		stackOld, stackNew = append(stackOld, head), append(stackNew, &Node{Val: head.Val})
		m[head], index, head = index, index+1, head.Next
	}
	if len(stackNew) == 0 {
		return nil
	}
	for i := 0; i < len(stackOld); i++ {
		if stackOld[i].Next != nil {
			stackNew[i].Next = stackNew[i+1]
		}
		if stackOld[i].Random != nil {
			stackNew[i].Random = stackNew[m[stackOld[i].Random]]
		}
	}
	return stackNew[0]
}

// 141
// https://leetcode-cn.com/problems/linked-list-cycle/
func HasCycle(head *ListNode) bool {
	if head == nil {
		return false
	}
	var arr = make(map[*ListNode]bool)
	for head != nil {
		if _, ok := arr[head]; ok {
			return true
		}
		arr[head] = true
		head = head.Next
	}
	return false
}

// 143
// https://leetcode-cn.com/problems/reorder-list/
func ReorderList(head *ListNode) {
	l, r := head, head
	for r != nil {
		if r.Next == nil {
			l, r, l.Next = head, l.Next, nil
			break
		}
		if r.Next.Next == nil {
			l, r, l.Next.Next = head, l.Next.Next, nil
			break
		}
		l, r = l.Next, r.Next.Next
	}

	var pre *ListNode
	for r != nil {
		pre, r, r.Next = r, r.Next, pre
	}
	for pre != nil {
		l, l.Next = l.Next, pre
		pre, pre.Next = pre.Next, l
	}
}

// 144
// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
func PreOrderTraversal(root *TreeNode) []int {
	var nodes []int
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		var node = stack[0]
		nodes = append(nodes, node.Val)
		stack = stack[1:]
		fmt.Println(node)
		if node.Right != nil {
			stack = append([]*TreeNode{node.Right}, stack...)
		}
		if node.Left != nil {
			stack = append([]*TreeNode{node.Left}, stack...)
		}
	}
	return nodes
}

// 145
// https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
func PostorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	res = append(res, PostorderTraversal(root.Left)...)
	res = append(res, PostorderTraversal(root.Right)...)
	res = append(res, root.Val)
	return res
}

// 146
// https://leetcode-cn.com/problems/lru-cache/
type LRUCache struct {
	capacity int
	list     *list.List
	data     map[int]*list.Element
}

type ListItem struct {
	Key, Value int
}

func LRUCacheConstructor(capacity int) LRUCache {
	return LRUCache{
		capacity,
		list.New(),
		make(map[int]*list.Element),
	}
}

func (this *LRUCache) Get(key int) int {
	if val, ok := this.data[key]; ok {
		this.list.MoveToBack(val)
		return val.Value.(ListItem).Value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if item, ok := this.data[key]; ok {
		this.list.MoveToBack(item)
		item.Value = ListItem{key, value}
	} else {
		if this.list.Len() >= this.capacity {
			delete(this.data, this.list.Front().Value.(ListItem).Key)
			this.list.Remove(this.list.Front())
		}
		this.list.PushBack(ListItem{key, value})
		this.data[key] = this.list.Back()
	}
}

// 152
// https://leetcode-cn.com/problems/maximum-product-subarray/
func MaxProduct2(nums []int) int {
	return 0
}

// 153
// https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
func FindMin(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		m := l + (r-l)/2
		if nums[m] < nums[r] {
			r = m
		} else {
			l = m + 1
		}
	}
	return nums[l]
}

// 154
// https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
func FindMin2(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		m := (l + r) / 2
		if nums[m] < nums[r] {
			r = m
		} else if nums[m] > nums[r] {
			l = m + 1
		} else {
			r--
		}
	}

	return nums[l]
}

// 155
// https://leetcode-cn.com/problems/min-stack/
type MinStack struct {
	items []int
	min   int
	index int
}

func MinStackConstructor() MinStack {
	return MinStack{items: make([]int, 10), index: -1}
}
func (m *MinStack) extend() {
	m.items = append(m.items, make([]int, 10)...)
}

func (m *MinStack) Push(x int) {
	if m.index == -1 {
		m.min = x
	} else if x < m.min {
		m.min = x
	}
	m.index++
	if m.index == len(m.items) {
		m.extend()
	}
	m.items[m.index] = x
}

func (m *MinStack) Pop() {
	var min, top = m.GetMin(), m.Top()
	m.index--
	if min == top && m.index >= 0 {
		min = m.items[0]
		for i := 1; i <= m.index; i++ {
			if min > m.items[i] {
				min = m.items[i]
			}
		}
		m.min = min
	}
}

func (m *MinStack) Top() int {
	if m.index > -1 {
		return m.items[m.index]
	}
	return 0
}

func (m *MinStack) GetMin() int {
	if m.index > -1 {
		return m.min
	}
	return 0
}

// 160
// https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
func GetIntersectionNode(headA, headB *ListNode) *ListNode {
	var p, q = headA, headB
	for p != nil || q != nil {
		if p == q {
			return p
		}
		if p != nil {
			p = p.Next
		} else {
			p = headB
		}
		if q != nil {
			q = q.Next
		} else {
			q = headA
		}
	}
	return nil
}

// 165
// https://leetcode-cn.com/problems/compare-version-numbers/
func CompareVersion(version1 string, version2 string) int {
	m, n := len(version1), len(version2)
	vi1, vi2, vn1, vn2 := 0, 0, 0, 0
	for vi1 < m || vi2 < n {
		vn1, vn2 = 0, 0
		for i := vi1; i < m; i++ {
			vi1 = i + 1
			if version1[i] == '.' {
				break
			} else {
				vn1 = vn1*10 + int(version1[i]-'0')
			}
		}
		for i := vi2; i < n; i++ {
			vi2 = i + 1
			if version2[i] == '.' {
				break
			} else {
				vn2 = vn2*10 + int(version2[i]-'0')
			}
		}
		if vn1 > vn2 {
			return 1
		}
		if vn1 < vn2 {
			return -1
		}
	}

	return 0
}

// TwoSum
// 167
// https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
func TwoSum(numbers []int, target int) []int {
	l, r := 0, len(numbers)-1
	s := 0
	for l < r {
		s = numbers[l] + numbers[r]
		if s == target {
			break
		} else if s < target {
			l++
		} else {
			r--
		}
	}
	return []int{l + 1, r + 1}
}

// 168
// https://leetcode-cn.com/problems/excel-sheet-column-title/
func ConvertToTitle(n int) string {
	var cols []rune
	for n > 26 {
		var m = n % 26
		n /= 26
		if m == 0 {
			n--
			m = 26
		}
		cols = append([]rune{rune(m + 64)}, cols...)
	}
	if n > 0 {
		cols = append([]rune{rune(n + 64)}, cols...)
	}
	return string(cols)
}

// 169
// https://leetcode-cn.com/problems/majority-element/
func MajorityElement(nums []int) int {
	var stack = make(map[int]int)
	for _, v := range nums {
		stack[v]++
		if stack[v] >= (len(nums)+1)/2 {
			return v
		}
	}
	return 0
}

// 171
// https://leetcode-cn.com/problems/excel-sheet-column-number/
func TitleToNumber(s string) int {
	var sum, base = 0, 1
	for i := len(s) - 1; i >= 0; i-- {
		sum += int(s[i]-64) * base
		base *= 26
	}
	return sum
}

// 172
// https://leetcode-cn.com/problems/factorial-trailing-zeroes/
func TrailingZeroes(n int) int {
	var num = 0
	for n >= 5 {
		num += n / 5
		n /= 5
	}
	return num
}

// 173
// https://leetcode-cn.com/problems/binary-search-tree-iterator/
type BSTIterator struct {
	nums  []int
	index int
}

func BSTIteratorConstructor(root *TreeNode) BSTIterator {
	var pre func(root *TreeNode)
	t := BSTIterator{[]int{}, 0}
	pre = func(root *TreeNode) {
		if root != nil {
			pre(root.Left)
			t.nums = append(t.nums, root.Val)
			pre(root.Right)
		}
	}
	pre(root)
	return t
}

func (b *BSTIterator) Next() int {
	b.index++
	return b.nums[b.index-1]
}

func (b *BSTIterator) HasNext() bool {
	return b.index <= len(b.nums)-1
}

// 179
// https://leetcode-cn.com/problems/largest-number/
func LargestNumber(nums []int) string {
	var res []string
	sort.Slice(nums, func(i, j int) bool {
		x, y := nums[i], nums[j]
		sx, sy := 10, 10
		for sx <= x {
			sx *= 10
		}
		for sy <= y {
			sy *= 10
		}
		return sy*x+y > sx*y+x
	})
	for _, v := range nums {
		res = append(res, strconv.Itoa(v))
	}
	return strings.Join(res, ``)
}

// Rotate
// 189
// https://leetcode-cn.com/problems/rotate-array/
func Rotate(nums []int, k int) {
	k %= len(nums)
	tmp := make([]int, k)
	copy(tmp, nums[len(nums)-k:])
	copy(nums[k:], nums)
	copy(nums, tmp)
}

// 190
// https://leetcode-cn.com/problems/reverse-bits/
func ReverseBits(num uint32) uint32 {
	var res uint32 = 0
	count := 1
	for num > 0 {
		if num%2 == 1 {
			res |= 1 << uint(32-count)
		}
		count++
		num = num >> 1
	}

	return res
}

// 191
// https://leetcode-cn.com/problems/number-of-1-bits/
func HammingWeight(num uint32) int {
	var sum = 0
	for num > 0 {
		if num%2 == 1 {
			sum++
		}
		num /= 2
	}
	return sum
}

// Rob2
// 198
// https://leetcode-cn.com/problems/house-robber/
func Rob2(nums []int) int {
	a, b := 0, 0
	for _, v := range nums {
		if a+v > b {
			a, b = b, a+v
		} else {
			a = b
		}
	}
	return b
}

// 199
// https://leetcode-cn.com/problems/binary-tree-right-side-view/
func RightSideView(root *TreeNode) []int {
	var view []int
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		var num = len(stack)
		for _, v := range stack {
			if v.Left != nil {
				stack = append(stack, v.Left)
			}
			if v.Right != nil {
				stack = append(stack, v.Right)
			}
		}
		view = append(view, stack[num-1].Val)
		stack = stack[num:]
	}
	return view
}
